/**
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
 * [1,2,3,6,4,5] 9
 * prev = 1
 * mp[[1: 1]]
 * 
 * prev = 3
 * mp[[1:1],[3:1]]
 * 
 * prev = 6
 * mp[[1:1],[3:1], [6:1]]
 * 
 * prev = 12
 * mp[[1:1],[3:2], [6:1]]
 * 
 * prev = 16;
 * mp[[1:1],[3:2],[6:1],[16:1]]
 * * prev = 21;
 * mp[[1:1],[3:2], [6:1],[16:1],[21:1]]
 * 这个比较难以理解，是一种动态规划思想
 */
var subarraySum = function (nums, k) {
    const mp = new Map();
    mp.set(0, 1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (mp.has(pre - k)) {
            count += mp.get(pre - k);
        }
        if (mp.has(pre)) {
            mp.set(pre, mp.get(pre) + 1);
        } else {
            mp.set(pre, 1);
        }
    }
    return count;
};

/**
 * 这个比较容易理解
 * 
 */
function subarraySumEasy(nums, k) {
    let count = 0;
    let right = 0;
    let left = 0;
    let temp = 0;
    while (right < nums.length) {
        temp += nums[right];
        //此时达到l指针应该走的条件:
        //条件是sum加和大于k，此时right指针不能走了
        //应该让left指针走，这样才能保证sum减小
        //当sum小于k时，此时再动right指针，最终找到新的加和子数组
        // 当temp大于k，说明可能有等于k的连续数组，
        // 那么将滑动窗口向右缩小
        while (temp > k) {
            temp -= nums[left];
            left++;
        }
        if (temp == k) count++;
        right++;
    }
    return count;
}

